package com.dataStruct;

import com.google.common.base.Preconditions;
import com.google.common.base.Strings;
import com.google.common.collect.Lists;
import com.google.common.collect.Maps;
import lombok.ToString;

import javax.annotation.concurrent.NotThreadSafe;
import java.util.HashMap;
import java.util.List;

/**
 * https://www.jianshu.com/p/6f81da81bd02
 * 使用工具统计内存占用数
 * 使用工具统计耗时
 * 寻找专业的java性能分析工具
 *
 * @author didi
 * @DESCRIPTION
 * @create 2019-04-14 14:27
 **/
@NotThreadSafe
public class Trie {

    private TrieTreeNode root = new TrieTreeNode('r');

    @Override
    public String toString() {

        List<String> strings = Lists.newArrayList();

        HashMap<Character, TrieTreeNode> children = root.children;

        final StringBuilder sb = new StringBuilder("{");
        sb.append("\"root\":").append(root);
        sb.append('}');
        return sb.toString();
    }

    @ToString
    class TrieTreeNode {

        public TrieTreeNode(char currentElement) {
            this.currentElement = currentElement;
            this.occur++;

            children = Maps.newHashMap();
        }

        private char currentElement;
        /**
         * 代表数据是否删除，该实现机制还是需要实际看使用场景，如果数据量大，但是更新少，可以直接物理删除
         * 如果数据量适中，更新多，采用逻辑删除
         * occur=0代表不存在，> 1代表存在多次
         */
        private int  occur;

        private HashMap<Character, TrieTreeNode> children;

    }

    public void insert(String data) {
        Preconditions.checkNotNull(!Strings.isNullOrEmpty(data), "input data is null");
        HashMap<Character, TrieTreeNode> current         = null;
        TrieTreeNode                     newTrieTreeNode = this.root;

        for (int i = 0; i < data.length(); i++) {
            current = newTrieTreeNode.children;
            Character currentChar = data.charAt(i);

            if (!current.containsKey(currentChar)) {
                newTrieTreeNode = new TrieTreeNode(data.charAt(i));
                current.put(data.charAt(i), newTrieTreeNode);
            } else {
                newTrieTreeNode = current.get(currentChar);
                if (i == data.length() - 1) {
                    newTrieTreeNode.occur++;
                }
            }
        }
    }

    public boolean delete(String data) {
        char[]                           chars           = data.toCharArray();
        HashMap<Character, TrieTreeNode> current         = null;
        TrieTreeNode                     newTrieTreeNode = this.root;

        for (int i = 0; i < chars.length; i++) {
            current = newTrieTreeNode.children;
            Character currentChar = chars[i];

            if (current.containsKey(currentChar)) {
                newTrieTreeNode = current.get(currentChar);
                if (i == chars.length - 1) {
                    newTrieTreeNode.occur--;
                }
            } else {
                break;
            }
        }
        return true;
    }

    /**
     * @param oldData
     * @param newData
     * @param
     * @return 0:操作失败，1:树中有oldData 更新成功 2:树中没有oldData，更新成功
     */
    public int update(String oldData, String newData) {

        int value = 0;

        if (contains(oldData)) {
            delete(oldData);
            insert(oldData);
            value = 1;
        } else {
            insert(oldData);
            value = 2;
        }
        return value;
    }

    public boolean contains(String data) {
        char[]                           chars           = data.toCharArray();
        HashMap<Character, TrieTreeNode> current         = null;
        TrieTreeNode                     newTrieTreeNode = this.root;

        boolean isexist = true;

        for (int i = 0; i < chars.length; i++) {
            current = newTrieTreeNode.children;
            Character currentChar = chars[i];

            if ((newTrieTreeNode = current.get(currentChar)) != null && newTrieTreeNode.occur > 0) {
                newTrieTreeNode.occur--;
            } else {
                isexist = false;
                break;
            }
        }
        return isexist;
    }

    //插入重复数据，occur没有加1
    //补充单元测试
    public static void main(String[] args) {
        //todo:内部类泛型有特殊的处理方法
        Trie trie = new Trie();
        trie.insert("string");
        trie.insert("string");
        System.out.println(trie);
    }
}
